

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:堆排序
 * 时间复杂度 O(nlogn)
 * 空间复杂度 O(1)
 * 稳定性 :稳定
 * User: 86183
 * Date: 2023-05-04
 * Time: 6:48
 */
public class sortDeom6 {
    public static void main(String[] args) {
        int [] a = {45,67,34,12,21,11};
         heapSort(a);
        System.out.println(Arrays.toString(a));
    }

    private static void heapSort(int[] a) {
        creatBigHeap(a);
        int end = a.length-1;
        while (end > 0){
            swap1(a,0,end);
            shiftDown(a,0,end);
            end--;
        }
    }

    private static void creatBigHeap(int[] a) {
        for (int parent = (a.length-1-1)/2;parent >= 0; parent--) {
            shiftDown(a,parent,a.length);

        }
    }

    private static void shiftDown(int[] a,int parent, int length) {
        int child = 2 *parent+1;
        while (child < length){
            if (child+1 < length && a[child] < a[child+1]){
                child++;
            }
            if(a[parent] < a[child]){
                swap1(a,parent,child);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    private static void swap1(int[] a, int parent, int child) {
        int tmp = a[parent];
        a[parent] = a[child];
        a[child] = tmp;
    }


}
